package offer_test_40;

//：数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。
//例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
//2出现的次数超过数组长度的一半，因此输出2.
public class nine_MoreThanHalfNum {
	public static void main(String[] args) throws Exception {
		int[] array = {1,2};
		System.out.println(findNumMoreThanHalf(array));
	}

	public static int findNumMoreThanHalf(int[] array) throws Exception {
		int k = 1;
		if (array.length == 0) {

			throw new Exception("array is empty");
		}
		int temp = array[0];
		for (int i = 1; i < array.length; i++) {
			if (k == 0) {
				temp = array[i];
				k++;
			}
			if (array[i] == temp) {
				k++;
			} else {
				k--;
			}
		}
		if (k > 0) {
			return temp;
		}else{
			throw new Exception("not have number that more than half");
		}
	}
}
